/*
 * @lc app=leetcode.cn id=116 lang=javascript
 *
 * [116] 填充每个节点的下一个右侧节点指针
 */

// @lc code=start
/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {Node} root
 * @return {Node}
 */
// 非递归版
// 在上一层，将下一层的子节点用next连接
// 然后将当前操作的节点移到下一层
// 通过刚才连接好的next节点，连接接下来的子节点
var connect = function(root) {
  if (!root) return null
  let leftmost = root
  while (leftmost.left) {
    let head = leftmost;
    while (head) {
      head.left.next = head.right

      if (head.next) {
        head.right.next = head.next.left
      }
      head = head.next
    }
    leftmost = leftmost.left
  }
  return root
};
// @lc code=end
// 递归版
//        O
//      /   \
//     O     O
//    / \   / \
//   O   O O   O
// 以这种结构为最小单位分析
// 就是 第二层的 roo1 和 root2为单位去连接，
// 那么递归的话，后面的子节点也都是这个结构
// var connect = function(root) {
//   if (!root) return null
//   linkNodeRight(root.left, root.right)
//   return root
// };

// var linkNodeRight = function (root1, root2) {
//   if (!root1) return
//   root1.next = root2
//   linkNodeRight(root1.left, root1.right)
//   linkNodeRight(root1.right, root2.left)
//   linkNodeRight(root2.left, root2.right)
// }

